{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 题目描述\n",
    "[P13. Roman to Integer](https://leetcode.com/problems/roman-to-integer/)\n",
    "\n",
    "Roman numerals are represented by seven different symbols: \n",
    "I, V, X, L, C, D and M.\n",
    "\n",
    "Symbol       Value\n",
    "I             1\n",
    "V             5\n",
    "X             10\n",
    "L             50\n",
    "C             100\n",
    "D             500\n",
    "M             1000\n",
    "\n",
    "For example, two is written as II in Roman numeral, just two one's added together. Twelve is written as, XII, which is simply X + II. The number twenty seven is written as XXVII, which is XX + V + II.\n",
    "\n",
    "Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:\n",
    "\n",
    "    I can be placed before V (5) and X (10) to make 4 and 9. \n",
    "    X can be placed before L (50) and C (100) to make 40 and 90. \n",
    "    C can be placed before D (500) and M (1000) to make 400 and 900.\n",
    "\n",
    "Given a roman numeral, convert it to an integer. Input is guaranteed to be within the range from 1 to 3999.\n",
    "\n",
    "Example 1:\n",
    "Input: \"III\"\n",
    "Output: 3\n",
    "\n",
    "Example 2:\n",
    "Input: \"IV\"\n",
    "Output: 4\n",
    "\n",
    "Example 3:\n",
    "Input: \"IX\"\n",
    "Output: 9\n",
    "\n",
    "Example 4:\n",
    "Input: \"LVIII\"\n",
    "Output: 58\n",
    "Explanation: L = 50, V= 5, III = 3.\n",
    "\n",
    "Example 5:\n",
    "Input: \"MCMXCIV\"\n",
    "Output: 1994\n",
    "Explanation: M = 1000, CM = 900, XC = 90 and IV = 4."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 解题思路\n",
    "首先找出解决此问题需要做那些转化，也就是分解此问题为几个小的问题。\n",
    "\n",
    ">1. 首先是需要一个map，需要将字母和数字对应起来，在Python自然是用dict。\n",
    ">2. 映射后并不能直接求和，因为有个前后的依赖关系。表面上看有些复杂，但是仔细看下可以发现规则只有一条：当后面的字母对应的数字大于前面的数字时（因为一般情况下都是从大到小，此时相反），这两个字母代表的数字就是大数减去小的数字。进一步地，可以看作就是前者的系数为-1，后者为1，其余无此依赖关系的系数均为1。且无论如何最后一个字母(如果存在)的系数也必为1。\n",
    ">3. 所以问题本质为加权和，而非简单的求和。问题关键就是求出所有的系数，之后直接对应相乘再相加即可。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Python代码[95.65%]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-01-20T13:19:46.907278Z",
     "start_time": "2019-01-20T13:19:46.891508Z"
    }
   },
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def romanToInt(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        # 映射\n",
    "        maps = {'I':1, 'V':5, 'X':10, 'L':50, 'C':100,\n",
    "                'D':500, 'M':1000}\n",
    "        units = [maps[u] for u in list(s)]\n",
    "        # 系数\n",
    "        factors = []\n",
    "        # 前后关系描述\n",
    "        for i in range(1, len(units)):\n",
    "            if units[i] > units[i-1]:\n",
    "                factors.append(-1)\n",
    "            else:\n",
    "                factors.append(1)\n",
    "        # 最后一个系数为1\n",
    "        factors.append(1)\n",
    "        result = sum(list(map(lambda t:t[0] * t[1] , zip(units, factors))))\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-01-20T13:20:30.525841Z",
     "start_time": "2019-01-20T13:20:30.497265Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1994"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 测试\n",
    "s = Solution()\n",
    "s.romanToInt(\"MCMXCIV\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 优秀代码学习[100%]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-01-20T13:22:47.393726Z",
     "start_time": "2019-01-20T13:22:47.378141Z"
    }
   },
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def romanToInt(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        romandict = {\n",
    "            \"I\": 1,\n",
    "            \"V\": 5,\n",
    "            \"X\": 10,\n",
    "            \"L\": 50,\n",
    "            \"C\": 100,\n",
    "            \"D\": 500,\n",
    "            \"M\": 1000\n",
    "        }\n",
    "        prev = 0\n",
    "        answer = 0\n",
    "        for i in s:\n",
    "            answer += romandict[i]\n",
    "            if romandict[i] > prev:\n",
    "                answer -= 2*prev\n",
    "            prev = romandict[i]\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-01-20T13:22:55.771053Z",
     "start_time": "2019-01-20T13:22:55.753462Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1994"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 测试\n",
    "s = Solution()\n",
    "s.romanToInt(\"MCMXCIV\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "上面的代码值得学习的地方是`prev`的引入，用其不断更新，以保留“前面的数字”，相对使用系数列表更加节省空间。此外，`answer -= 2*prev`使得前面所说的“加权求和”在一次遍历中就得以实现，节省了时间。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.6"
  },
  "toc": {
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": true
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
